package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class DecodeString {

  public static void main(String[] args) {
    Solution solution = new DecodeString().new Solution();
    // put your test code here
    System.out.println(solution.decodeString("3[a2[dc]]"));
  }
  // leetcode submit region end(Prohibit modification and deletion)

  // leetcode submit region begin(Prohibit modification and deletion)
  class Solution {
    public String decodeString(String s) {
      // 本题中的难点在于，括号中 会内嵌括号
      // 没看懂，多看几次 o(╯□╰)o
      Deque<Integer> stack_num = new LinkedList<>(); // 存储需要重复字符串的数字
      Deque<String> stack_res = new LinkedList<>(); // 存储待重复的字符串
      StringBuilder res = new StringBuilder();
      int num = 0;

      for (Character x : s.toCharArray()) {
        if (x == '[') {
          stack_num.push(num); // 把括号前的数字压栈
          stack_res.push(res.toString()); // 把括号前的字母——即将来等待被重复的字符串压栈
          // 需重复数字归零（注意！因为 num 可能会是n位数，为了方便后续统一x10处理，必须归零
          num = 0;
          res = new StringBuilder(); // res 也要重置
        } else if (x == ']') {
          int cur_num = stack_num.pop(); // 此次要重复的次数数字
          String last_res = stack_res.pop(); // 紧贴着这一组括号外的还没执行重复的字符串
          StringBuilder tmp = new StringBuilder(); // 本次要重复的完整子串
          for (int i = 0; i < cur_num; i++){
            tmp.append(res);
          }
          res = new StringBuilder(last_res + tmp);
        } else if (x >= '0' && x <= '9') {
          num = num * 10 + (x - '0'); // 把字符数字转换为数字
        } else {
          res.append(x);
        }

      }

      return res.toString();

    }
  }
}
